package com.nine.face.sort;

import java.util.Arrays;

/**
 * 单边循环
 */
public class QuickSort1 {

    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        //partition(a, 0, a.length - 1);
        quick(a, 0, a.length - 1);
    }

    // 提供递归方法
    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        // 一趟快速排序，返回基准点索引
        int p = partition(a, l, h);
        // 左边分区范围
        quick(a, l, p - 1);
        // 右边分区范围
        quick(a, p + 1, h);
    }

    /**
     * @param a
     * @param l
     * @param h
     * @return 返回值代表基准点元素所在的正确索引，用它来确定下一轮分区的边界
     */
    private static int partition(int[] a, int l, int h) {
        // 基准点，这里选择最后一个元素
        int pv = a[h];
        int i = l;
        // 一趟快速排序，将小于基准点的元素放到左边，大于的放在右边
        for (int j = l; j < h; j++) {
            if (a[j] < pv) {
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
            }
        }
        if (i != h) {
            swap(a, i, h);
        }
        System.out.println("一趟排序后：" + Arrays.toString(a) + "" + "基准点索引：" + i);
        return i;
    }

    // 交换数组元素
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
